import java.util.*;

class Student implements Comparable<Student> {
    public int age;
    public String name;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
                        //  equals 和 hashCode 总是成对出现
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

    @Override   //重写object类中的compareTo方法，
                //  这种不好的地方就在于写死了，不方便改动了 所以我们提供给了比较器
    public int compareTo(Student o) {

        //return this.age - o.age;   //这是小根堆的情况，反过来就是大根堆
        return o.age - this.age;   //这就是大根堆了
    }


    /**
     *
     *  这是我自己写的，不一定正确

     public int compareTo2(Student o) {
        return this.name.compareTo(o.name);
    }
     */
}

//这是提供了姓名比较器，若是比较姓名，可以调用这个比较器，注意需要重写compare方法
class NameComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.name.compareTo(o2.name);  //注意此处compareTo 是调用String的compareTo
    }
}

//这是提供了年龄比较器，若是比较年龄，可以调用这个比较器，注意需要重写compare方法
class AgeComparator implements Comparator<Student> {


    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }
}

class LargeComparator2 implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        //return o1 - o2; //这是小根堆

       // return o2 - o1;  //注意引用类型还是用compareTo，用减号的话，有可能行，但是也有可能会出问题
        return o2.compareTo(o1);
    }
}

class LargeComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //return o1.age - o2.age; //这是小根堆

        return o2.age - o1.age;
    }
}
public class Test {
    public static void main10(String[] args) {
        TestHeap testHeap = new TestHeap();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = testHeap.topKFrequent(words,3);
        System.out.println(ret);
    }







    public static void main6(String[] args) {
        Student student1 = new Student("zhangsan",10);
        Student student2 = new Student("zhangsan",20);


        LargeComparator largeComparator = new LargeComparator();
        //这是默认小根堆，传入比较器变成大根堆  (根据年龄的，可比较的)
        Queue<Student> priorityQueue = new PriorityQueue<>(largeComparator);
        priorityQueue.offer(student1);
        priorityQueue.offer(student2);

        System.out.println("fasfa");

        //这是把官方提供的小根堆改成了大根堆
        LargeComparator2 largeComparator2 = new LargeComparator2();
        Queue<Integer> priorityQueue3 = new PriorityQueue<>(largeComparator2);
        priorityQueue3.offer(1);
        priorityQueue3.offer(2);

        System.out.println("fasfa");

        //上述传入比较器的方法，也可以利用匿名内部类的方式来传入
        Queue<Student> priorityQueue2 = new PriorityQueue<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o2.age - o1.age;
            }
        });
        priorityQueue2.offer(student1);
        priorityQueue2.offer(student2);

        System.out.println("=======");

        Queue<Integer> priorityQueue4 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);  //这就是大根堆了
            }
        });
        priorityQueue4.offer(4);
        priorityQueue4.offer(5);

        System.out.println("========");

        //这是利用了lambda表达式来写的，后面已经看过来了，所以这里也可以理解
        Queue<Integer> priorityQueue5 = new PriorityQueue<>
                ((o1,o2) -> {return o2.compareTo(o1);} );   //这就是实现了大根堆
        priorityQueue5.offer(7);
        priorityQueue5.offer(8);

        System.out.println("========");
    }








    public static void main7(String[] args) {
        Student student1 = new Student("zhangsan",10);
        Student student2 = new Student("zhangsan",20);
        System.out.println(student1 == student2);
        System.out.println(student1.equals(student2));

        System.out.println(student1.compareTo(student2));

        NameComparator nameComparator = new NameComparator();
        int ret = nameComparator.compare(student1,student2);
        System.out.println(ret);

        AgeComparator ageComparator = new AgeComparator();
        int ret2 = ageComparator.compare(student1,student2);
        System.out.println(ret2);

    }


    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initElem(array);
        testHeap.createHeap();
        //testHeap.offer(80);
        testHeap.pop();
        System.out.println("fasfaaaaaff");

        List<Integer> list = new ArrayList<>();
        //默认是小根堆
        //看源码可知，只要是实现了collection接口的，都是可以传递的
        Queue<Integer> priorityQueue = new PriorityQueue<>(list);

    }

    public static void main9(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initElem(array);
        testHeap.createHeap();


        testHeap.heapSort();
        System.out.println("fasda");

    }


    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] elem = {1,5,43,3,2,7,98,41,567,78};
        int[] ret = testHeap.smallestK(elem,3);
        System.out.println(Arrays.toString(ret));

        testHeap.heapSort();
        System.out.println("fasda");


    }


    //力扣17.14. 求数组中最小的k个数 (中等题目) (不是top-k 的思路)
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null && 0 == k) {
            return ret;
        }
        Queue<Integer> queue = new PriorityQueue<>();
        //堆中放入数组元素  小根堆
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
        }
        //弹出前k个即可
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

}
